package fun.ticsmyc.dataStructure;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Ticsmyc
 * @package fun.ticsmyc.dataStructure
 * @date 2020-08-18 20:42
 */
public class LRU手写 {

    private Map<Integer,Node> map;
    private Node head;
    private Node tail;
    private int capacity;
    private int size;

    public LRU手写(int capacity) {
        map = new HashMap<>(capacity);
        head=new Node(0,0);
        tail=new Node(0,0);
        head.next = tail;
        tail.pre = head;
        this.capacity=capacity;
        size =0;
    }

    private void remove(Node node){
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }
    private void insert(Node node){
        head.next.pre =node;
        node.next = head.next;
        head.next = node;
        node.pre = head;
    }
    private void judge(){
        if(size >capacity){
            Node temp = tail.pre;
            //删链表
            remove(temp);
            //删map
            map.remove(temp.key);
            size--;
        }
    }

    public int get(int key) {
        //1.从map中取到key
        Node node = map.get(key);
        if(node ==null){
            return -1;
        }
        //2.链表中删除key
        remove(node);
        //3.链表中插入key
        insert(node);
        return node.val;
    }

    public void put(int key, int value) {
        Node node = new Node(key,value);
        if(map.containsKey(key)){
            //如果已经有过这个key，更新map 和链表就可以
            Node last = map.get(key);
            remove(last);
            map.put(key,node);
            insert(node);
            return;
        }
        //1.链表中插入key
        insert(node);
        //2.map中插入key
        map.put(key,node);
        size++;
        //3.是否需要删除
        judge();
    }


    public void print() {
        Node cur = head.next;
        while(cur != tail){
            System.out.print(cur.key+"--"+cur.val+" ");
            cur=cur.next;
        }
    }

    public static void main(String[] args) {
        LRU手写 map = new LRU手写(2);
        map.put(2,1);
        map.put(1,1);
        map.put(2,3);
        map.put(4,1);
        map.print();
        System.out.println();
        map.get(2);
        map.print();
        System.out.println();
        map.get(1);
        map.print();
    }

    private class Node{
        Node pre;
        Node next;
        int val;
        int key;
        public Node(int key ,int val){
            this.val = val;
            this.key=key;
        }
    }
}
